""" sbak/tree.py - General-purpose tree structures.

    The purpose of this module is to provide a basis for implementing
    data structured in tree-like hierarchies using objects that have
    the following qualities:
    
    - Each banch node may have any number of sub nodes.
    - Any node may be added to any branch node and later removed using
      simple interfaces.
    - Each branch node must keep subnodes in order. (Think lists, not sets.)
    - Each node must be able to indicate its parent node.
    - Each node must have only one parent, or else no parent at all.
    - Each sub node (child) cannot appear in a super node (parent)
      more than once. (Think sets, not lists.)
    
    The classes defined here are intended for use as bases or mixins.
    The only data they store is that which is needed to keep track of
    relations between each other.
"""

from operator import attrgetter

import sbak.base

class AbstractNode(sbak.base.Object):
    """ Abstract base for all node types.
    
        Defines attributes and behavior common to all types of node.
    """
    
    __slots__ = ['_parent', '_id', '_localid', 'tag', 'tags']
    
    tag = 'node'
    tags = set()
    
    def __init__(self, id = None, localid = None, tag = None, tags = None):
        self._id = None
        self._localid = None
        self._parent = None
    
        self.id = id
        self.localid = localid
        if tag is not None:
            self.tag = tag
        if tags is not None:
            self.tags = set(tags)
    
    def __repr__(self):
        return '<%s%s%s at 0x%x>' % (
            self.__class__.__name__,
            " " + self.id if self.id is not None else "",
            " in "+repr(self.parent) if self.parent is not None else "",
            id(self)
        )
    
    _doc_id =\
    """ Unique string identifier for a node.
    
        Only one node in an entire tree should ever have a particular
        ID string. However, it is also permissible to give None as the
        ID, or to delete the ID. This indicates that the node has no
        ID at all, so it is fine for multiple nodes to use None as the
        ID.
        
        All values assigned to this property, except for None, will be
        converted to strings. Deleting the property has the same effect
        as setting it to None.
    """
    _fget_id = attrgetter('_id')
    def _fset_id(self, val):
        val = str(val) if val is not None else None
        self._id = val
    def _fdel_id(self):
        self._id = None
        
    _doc_localid =\
    """ Lesser unique identifier for a node.
    
        Only one node in a branch should ever have a particular local
        ID string. However, multiple nodes may share the same local ID
        if each of those nodes is in a separate branch. This is because
        a local ID is local to the node's parent branch and not the
        entire tree.
        
        If the local ID is set to None or deleted (which actually just
        sets it to None) then the node is said not to have a local ID.
        Therefore, it is fine for multiple nodes in the same branch to
        have an ID of None.
        
        All values assigned to this property, except for None, will be
        converted to strings. Deleting the property has the same effect
        as setting it to None.
    """
    _fget_localid = attrgetter('_localid')
    def _fset_localid(self, val):
        val = str(val) if val is not None else None
        self._localid = val
    def _fdel_localid(self):
        self._localid = None
    
    def set_parent_internal(self, parent):
        """ Internally changes the parent of the leaf to the given obj.
        
            The leaf is not appended to the parent; it is assumed that
            this will be done afterwards using parent.append_internal.
            
            Note that the leaf will be removed from its previous parent
            node as a side effect of changing parents.
        """
        if self._parent is not None and self._parent is not parent:
            self._parent.remove_internal(self)
        self._parent = parent
    
    def set_parent(self, parent):
        """ Changes the parent of the leaf to the given value.
        
            Does nothing if the given object is the current parent.
        """
        if parent is not self._parent:
            if parent is not None:
                parent.append_internal(self)
            self.set_parent_internal(parent)
    
    parent = property(
        fget = attrgetter('_parent'),
        fset = set_parent,
        doc =
        """ The current parent of the leaf.
        
            If the leaf has no parent, this will be None.
        
            Setting this is the same as calling
            leaf.set_parent(parent)
        """
    )
    
    def get_root(self):
        """ Returns the root node for this leaf's tree.
        
            If the parent is None, this returns self.
            
            If the tree is cyclic, or if it is badly linked, this
            returns None to indicate that there is no "top-level" node
            anywhere in the tree.
        """
        root = self
        parents = [root]
        while root.parent is not None:
            root = root.parent
            if root in parents:
                return None
            parents.append(root)
        return root
    
    def get_sibling(self, N):
        """ Retuns the Nth sibling "to the right" of this node.
        
            If 0 is passed, returns self.
            If a negative is passed, a sibling to the left is returned.
            
            AttributeError may be raised if the node has no parent.
            IndexError may be raised if the index value given indicates
            a position outside the parent node.
        """
        return self._parent[self._parent.index(self)+N]
    
    def set_id_safe(self, newid):
        """ Safely sets or changes the ID string of the leaf.
        
            This is "safe" because the entire tree will be scanned for
            other leaves/nodes that have the same ID, and the new ID
            will be applied if (and only if) the ID is not in use by
            any other. If the exact ID is already being used, then a
            ValueError is raised and this leaf's ID is not changed.
            
            NOTE 1: The process of scanning the entire tree for IDs can
            be time-consuming, so it is recommended that you only
            use this method when you know there is a reasonable chance
            that an ID may be duplicated somewhere.
            
            FIXME: This method may not be able to work correctly in
            some complex cyclicly-linked trees, incorectly setting
            IDs when it should not.
        """
        def check_id(self, id, nodes):
            if self.id == newid:
                raise ValueError
            try:
                for child in self:
                    if child in nodes:
                        return
                    nodes.append(child)
                    check_id(child, newid, nodes)
            except TypeError:
                pass
        
        root = self.get_root()
        if root is None:
            root = self.parent
            if root is None:
                root = self
        try:
            check_id(root, newid, [])
        except ValueError:
            raise ValueError("id %s already in use." % repr(newid))
        
        self.id = newid
    
    def kill(self):
        """ Removes the Leaf from its parent.
            
            Same as `leaf.parent = None`. Safe to call multiple times.
        """
        self.parent = None
    
    def destroy(self):
        """ Kills the leaf.
        
            In theory, this would call destroy() for all of the leaf's
            children. But since leaves cannot have children, this just
            calls self.kill().
        """
        self.kill()

class Leaf(AbstractNode):
    """ An end node.
    
        leaf = Leaf( id = None )
    
        A leaf can have a parent, but cannot have children. It is
        intended for situations where a branch must be terminated.
        
        ~~~ Attributes ~~~
        
        Objects of the Leaf class cannot have any attributes
        besides those listed here (though Leaf subclasses may).
        
        id:         An identifying string for this Leaf within its
                    tree. No two leaves in the same tree, regardless
                    of where they are in the tree, should have the
                    same ID string. *Note 1* If a leaf has no ID, this
                    should be None.
        
        tag:        A string that indicates what "kind" of leaf or node
                    this is. It doesn't have to be the same as the
                    class name, but leaves/nodes having the same tag
                    should have generally the same behavior. (The
                    exact behavior depends on the usage of the
                    leaf/node.)
        
        _parent:    Internal reference to the parent. If you intend to
                    move the leaf to a different super node, do not
                    modify this directly as it may result in a badly-
                    linked tree. Instead, use the .set_parent method or
                    the .parent property.
                    
        ~~~ Notes ~~~
        
        1.  In future implementations this restriction may be forced,
            but it isn't now, so you are on your own to make sure that
            there are no conflicting IDs within a tree.
    """
    
    tag = 'leaf'
    
    def __init__(self, id=None, localid=None, tag=None, tags=None):
        super(Leaf,self).__init__(id=id, localid=localid, tag=tag, tags=tags)

class Branch(AbstractNode):
    """ A generic branch.
    
        branch = Branch(
            [
                Leaf(),   # or Branch([...])
                Leaf(),   # ...
                ...
            ],
        
            id = None
        )
        
        Branch extends AbstractNode by adding support for subnodes, or
        "children." Children are treated much like items in a set or
        list, and the appropriately-named methods can be used to access
        them.
        
        A node can be accessed like a sequence type in order to access
        a child by its index value. Similar to a Python sequence, a
        negative index value may be used to access a child from the end
        of the node rather than from the beginning.
        
        An immediate child of a node may be acquired by giving the ID
        of the child as a key. A KeyError may be raised if no
        immediate child of the node has the key as its ID. At this
        time children can NOT be replaced by ID; attempting to do so
        will result in a TypeError.
        
        Assignment to a position in the node will replace the leaf at
        that position with the new leaf. The old leaf will be removed
        from the node and its parent will be set to None. The new leaf
        will be removed from its previous node and added to the current
        one. The new leaf's parent will be updated to be the current
        node.
        
        A child cannot be replaced by another child if the second child
        is already in the node. (However, attempting to replace a child
        with itself is ignored, since the net effect of this operation
        would be nothing.)
        
        Deleting a child from the node is the same as replacing a
        child, except that no new child fills its place and the "gap"
        left by the removed child collapses and disappears.
        
        There is read-only support for slicing, but lists are returned
        rather than nodes. Slice assignment and deletion may be added
        at a later time.
        
        Note that unlike a list or tuple, a node cannot contain the
        same leaf more than once. Attempting to append a child that is
        already in the node will result in a ValueError being raised.
        The set-like .add method is available for silently ignoring
        attempts to add children that are already in the node. The
        .remove, .discard, .index, .update, and .extend methods are
        also available.
        
        ~~~ Attributes ~~~
        
        transparent:    Though this attribute does not effect the
                        behavior of the node in any way, Branchs that
                        are marked as "transparent" (ie. those whose
                        `transparent` attribute is set to True) should
                        be "skipped over" in tree-climbing operations
                        performed by children of the node in whatever
                        way appropriate for the operation.
                        TODO: Explain further.
    """
    
    __slots__ = ['_children', 'transparent']
    
    def __init__(self, children=(), id = None, localid=None, tag=None,
                 tags=None):
        AbstractNode.__init__(self, id=id, localid=localid, tag=tag, tags=tags)
        self._children = []
        for c in children:
            self.append(c)
        self.transparent = False
    
    def __repr__(self):
        return "<%s %s with %i children at 0x%x>" % (
            self.__class__.__name__,
            repr(self.id) if self.id is not None else "(no id)",
            len(self),
            id(self)
        )
    
    def __getitem__(self, i):
        children = self._children
        try:
            return children[i]
        except TypeError:
            for child in children:
                if child.localid == i or child.id == i:
                    return child
            raise KeyError("no child with index, localid, or id %r" % i)
        
    def __setitem__(self, i, v):
        if isinstance(i, slice):
            raise TypeError("slice assignment on Node not supported.")
        self.replace(i, v)
        
    def __delitem__(self, i):
        if isinstance(i, slice):
            raise TypeError("slice deletion on Node not supported.")
        child = self[i]
        self.remove(child)
        
    def __iter__(self):
        return iter(self._children)
    
    def __contains__(self, child):
        return child in self._children
    
    def __len__(self):
        return len(self._children)
    
    def append_internal(self, child, index=None):
        """ Appends a child leaf internally.
        
            child:  The child to append.
            
            index:  Used to change the append into an insert. If None
                    is passed, an append is done, otherwise the child
                    will be inserted at the indicated position.
        
            This will not update the parent of the leaf; it is
            assumed that the leaf's .set_parent_internal method
            will be called.
            
            ValueError is raised if an attempt is made to append a
            child that is already in the node.
        """
        if child in self._children:
            raise ValueError("cannot append %s; already contained." %
                             repr(child))
        if index is None:
            self._children.append(child)
        else:
            self._children.insert(index, child)
    
    def append(self, child):
        """ Appends a child leaf to the node.
        
            This will update the parent of the leaf. A side effect of
            this is that the leaf will be removed from its previous
            node. (Leaves cannot belong to two different nodes at
            once.)
            
            If an attempt is made to append a leaf that is already in
            the node, a ValueError is raised.
            
            WARNING: No checks are performed to prevent cyclicly-linked
            trees. However, the Leaf.get_root method can detect them to
            prevent infinite looping.
        """
        self.append_internal(child)
        child.set_parent_internal(self)
    
    def insert(self, index, child):
        """ Inserts a leaf into the node at the given index position.
        
            The child leaf must not already exist in the node. If it
            does, ValueError will be raised. Otherwise, the leaf will
            be removed from its current parent node and inserted into
            this one at the given position.
        """
        self.append_internal(child, index)
        child.set_parent_internal(self)
    
    def add(self, child):
        """ Adds a child leaf to the node.
        
            This will update the parent of the leaf. A side effect of
            this is that the leaf will be removed from its previous
            node. (Leaves cannot belong to two different nodes at
            once.)
            
            If the child is already in the node, nothing happens.
            
            WARNING: No checks are performed here to prevent cyclicly-
            linked trees.
        """
        try:
            self.append_internal(child)
            child.set_parent_internal(self)
        except ValueError:
            pass
    
    def remove_internal(self, child):
        """ Removes a child leaf from the node internally.
        
            This will not update the parent of the leaf; it is assumed
            that the leaf's .set_parent_internal method will be called.
            
            Attempting to remove a child that is not a part of the node
            will result in a ValueError.
        """
        self._children.remove(child)

    def remove(self, child):
        """ Removes a child leaf from the node.
        
            The child's parent will be changed to None.
            
            Attempting to remove a child that is not a part of the node
            will result in a ValueError.
        """
        if child not in self._children:
            raise ValueError("cannot remove child; not in node.")
        child.set_parent_internal(None)
    
    def discard(self, child):
        """ Discards a child leaf.
        
            The child's parent will be changed to None.
            
            Attempting to remove a child that is not a part of the node
            will have no effect on either the node or the leaf.
        """
        try:
            self.remove(child)
        except ValueError:
            pass
    
    def extend(self, children):
        """ Appends each child in the given sequence to the node.
        
            The given argument must be an iterable sequence, and each
            item in the sequence must be a unique leaf. Also, the
            sequence cannot contain any leaf that is already a child of
            the node.
            
            TypeError may be raised if the given argument is not
            iterable.
            
            ValueError may be raised if the given sequence contains
            a leaf more than once or if it contains any leaf that is
            already a child of the current node.
        """
        all = tuple(children) + tuple(self)
        for c in all:
            if all.count(c) > 1:
                raise ValueError("cannot extend; duplicate values may exist.")
        for child in children:
            self.append_internal(child)
            child.set_parent_internal(self)
    
    def update(self, children):
        """ Adds each child in the given sequence to the node.
        
            The given argument must be an iterable sequence. Each item
            must be a leaf. Even if a sequence contains the same leaf
            multiple times, the leaf is only added once. Leaves in the
            sequence that are already a part of the node will be
            ignored.
            
            TypeError may be raised if the argument given is not
            iterable.
        """
        for c in children:
            try:
                self.append_internal(c)
                c.set_parent_internal(self)
            except ValueError:
                pass
    
    def replace(self, old, new):
        """ Replace a child with a new one.
        
            old:    Existing child, index of, or leaf ID of. If it is a
                    number, it is interpreted as an index. If it is a
                    string, it will be interpreted as a leaf ID string.
                    If it is an object that is a child of the node, it
                    is unprocessed. Other types of value have undefined
                    behavior, though they MIGHT still work if there is
                    a child that uses the value as its ID.
            
            new:  The child to replace the old child.
            
            The old child must exist in the node, or else a KeyError
            may occur.
            
            The new child must not already be in the tree, or else a
            ValueError may occur.
        """
        try:
            old = self[old]
        except KeyError:
            if old not in self:
                raise KeyError("%s not contained in branch." % repr(old))
        if new in self:
            raise ValueError("cannot replace child %s; new child %s"
                             "already contained in branch." %
                             (repr(old), repr(new)))
        index = self.index(old)
        self.remove(old)
        self.insert(index, new)
    
    def index(self, child):
        """ Returns the index position of the child leaf.
        
            Raises ValueError if the child is not a child of this node.
        """
        return self._children.index(child)
    
    def find_by_id(self, id, _nodes=None):
        """ Returns the child with the given ID if present.
        
            id:     The ID string of the child to find.
            
            _nodes: Internal argument; do not pass this directly.
        
            This will search for a child with the given ID among the
            children of the current branch, among the children of the
            children, and so on until the end of every branch of the
            tree below until the current branch has been reached. This
            will NOT search among parents, grandparents, etc.
            
            NOTE: It is especially important here that no two nodes in
            a tree have the same ID because the child returned in the
            case of an ID conflict is undefined.
            
            TIP: If you only want to search for immediate children
            within the current branch but not within children of the
            children, etc. then use node subscripting with the ID of
            the desired child as the key. This is usually faster.
            For example:
            
            >>> node['some_child']
            <leaf 'some_child' at 0x...>
            
            This method will attempt to prevent against OverflowErrors
            when searching through a cyclicly-linked tree by
            maintaining a list of children already searched. Badly-
            linked trees are not detected, however, so an incorrect
            result may be returned in that case.
            
            If a child is not found anywhere within or below the
            current branch, None is returned.
        """
        if _nodes is None: _nodes = []
        for child in self:
            if child in _nodes:
                return None
            _nodes.append(child)
            if child.id == id:
                return child
            try:
                subfind = child.find_by_id
            except AttributeError:
                pass
            else:
                return subfind(id, _nodes)

    def find_by_tag(self, tag, _nodes=None, _matches=None):
        """ Like `find_by_id`, but searches based on tag.
            
            tag:    Tag to search for. All children, grandchildren,
                    etc. with the given tag will be returned in a
                    list.
            
            _nodes:
            _matches:   Internal arguments; do not pass these directly.
        
            Returns a list containing 0 or more nodes.
        """
        if _nodes is None: _nodes = []
        if _matches is None: _matches = []
        for child in self:
            if child in _nodes:
                return None
            _nodes.append(child)
            if tag in set(child.tags).union((child.tag,)):
                _mathces.append(child)
            try:
                subfind = child.find_by_tag
            except AttributeError:
                pass
            else:
                subfind(id, _nodes, _matches)
        return _matches

    def kill(self):
        """ Removes the branch from its parent and orphans children.
            This is safe to call multiple times.
        """
        for child in self[:]:
            self.remove(child)
        Leaf.kill(self)
    
    def destroy(self):
        """ Kills children recursively, then kills self.
        
            This has the same effect as kill(), but it is called
            recursively on every child, and only after all children
            are destroyed will the original branch itself be killed.
        """
        for child in self:
            child.destroy()
        self.kill()
